//
//  BacktrackSequence.m
//  iOS-Learning-Demo
//
//  Created by yuan xiaodong on 2022/3/29.
//  Copyright © 2022 yuan. All rights reserved.
//

#import "BacktrackSequence.h"

@implementation BacktrackSequence

/**
 矩阵中的路径
 请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一格开始，每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格，那么该路径不能再次进入该格子。例如，在下面的3×4的矩阵中包含一条字符串“bfce”的路径（路径中的字母用加粗标出）。

 [[“a”,“b”,“c”,“e”],

 [“s”,“f”,“c”,“s”],

 [“a”,“d”,“e”,“e”]]

 但矩阵中不包含字符串“abfb”的路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入这个格子。

 示例 1：

 输入：board = [["A","B","C","E"],
             ["S","F","C","S"],
             ["A","D","E","E"]], word = "ABCCED"
 输出：true
 1
 2
 3
 4
 示例 2：

 输入：board = [["a","b"],
             ["c","d"]], word = "abcd"
 输出：false
 */

+ (void)testExist{
    NSMutableArray *boards = @[@[@"A",@"B",@"C",@"E"],
                               @[@"S",@"F",@"C",@"S"],
                               @[@"A",@"D",@"E",@"E"]].mutableCopy;
    BOOL result = [self exist:boards word:@"ABCCED"];
    NSLog(@"%@",result?@"YES":@"NO");
}

+ (BOOL)exist:(NSMutableArray <NSMutableArray *>*)board word:(NSString *)word{
    /*首先矩阵的长宽需要被求出来
    按照某一逻辑在board中寻找word的第一个字符
    找到后开始查询上下左右有无下一个字符
    有则继续
    无则返回上一层，重新找有无该字符
    如果最终寻找结束，到了'\0'，则成功
    否则失败
    中间的这一部分应该是一个有输入有输出的函数，可以不断记录位置和结果
    通过某一个备份字符，不断判断是否和word相等，相等则ture
    */
    //判断矩阵是否为空等边界条件
    NSMutableArray *words = @[].mutableCopy;
    for (int i = 0 ; i < word.length ; i ++){
        words[i] = [NSString stringWithFormat:@"%c",[word characterAtIndex:i]];
    }
    
    //程序中定义新布尔值的方法，标注对应坐标的的元素是否被访问过。
    NSMutableArray *isVisited = @[@[@0,@0,@0,@0].mutableCopy,
                                  @[@0,@0,@0,@0].mutableCopy,
                                  @[@0,@0,@0,@0].mutableCopy].mutableCopy;
    
    for (NSInteger i = 0 ; i < board.count ; i ++){
        for (NSInteger j = 0 ; j < board[0].count ; j ++){
            NSString *itemStr = [NSString stringWithFormat:@"%@",board[i][j]];
            NSString *firstStr = [NSString stringWithFormat:@"%@",words[0]];
            if ([itemStr isEqualToString:firstStr]){
                if ([self dfs:board i:i j:j isVisited:isVisited words:words index:0]) return true;
            }
        }
    }
    return false;
}

+ (BOOL)dfs:(NSMutableArray <NSMutableArray *>*)board i:(NSInteger)i j:(NSInteger)j isVisited:(NSMutableArray *)isVisited words:(NSMutableArray *)words index:(NSInteger)index{
    if (index == words.count) return true;
    
    //进入下面的条件则说明搜索超出边界，只能找到找过的元素，找不到，这几种情况，失败
    
    if (i < 0 || j < 0 || i == board.count || j == board[0].count || [isVisited[i][j] boolValue] || ![[NSString stringWithFormat:@"%@",board[i][j]] isEqualToString:[NSString stringWithFormat:@"%@",words[index]]]) return false;
    
    //如果没有落入上一条，则已经找到一个元素了，因此将falg设真
    isVisited[i][j] = @1;
    
    //四个方向，下，上，右，左，全都找一遍，没有的话就返回
    BOOL res =  [self dfs:board i:i+1 j:j isVisited:isVisited words:words index:index + 1] ||
                [self dfs:board i:i - 1 j:j isVisited:isVisited words:words index:index + 1] ||
                [self dfs:board i:i j:j+1 isVisited:isVisited words:words index:index + 1] ||
                [self dfs:board i:i j:j - 1 isVisited:isVisited words:words index:index + 1];
    
    isVisited[i][j] = @0;
    
    return res;
}


@end
